iT邦幫忙

2022 iThome 鐵人賽

DAY 3
0

首先是 2413. Smallest Even Multiple (easy)
https://leetcode.com/problems/smallest-even-multiple/

要求回傳一個2與n的最小公倍數,標準送分題
想法:

  1. 驗證n是否為2的倍數
  2. 不是就n*2回傳
class Solution:
    def smallestEvenMultiple(self, n: int) -> int:
        return n*2 if n%2 else n

接著是 2414. Length of the Longest Alphabetical Continuous Substring (medium)
https://leetcode.com/problems/length-of-the-longest-alphabetical-continuous-substring/

要求要找出 字母連續子字串
也就是"abcdefghijklmnopqrstuvwxyz"的子字串(姑且稱為aC)
想法1,直接暴力解:
1.把s裡的第一個當作起始字母
2.檢驗s[i]在aC裡的索引質是否為s[i-1]的下一個索引值
3.不是的話就把s[i]當成起始字母
4.是的話count + 1

class Solution:
    def longestContinuousSubstring(self, s: str) -> int:
        aC = "abcdefghijklmnopqrstuvwxyz"
        temp,c,maxC = aC.index(s[0]),1,1
        for i in range(1,len(s)):
            if aC.index(s[i])-1 != temp:
                temp = aC.index(s[i])
                c=1
            else:
                temp = aC.index(s[i])
                c+=1
            maxC = max(maxC,c)
        return maxC    

這是一開始我寫出的樣貌,但由於有點趕時間所以寫的比較隨便一點,這樣寫由於.index()的關係,花費的時間其實會很久。
後來想到其實有一個函式叫做ord(),可以直接把字母轉成ASCII處理,一樣可以算出大小關係。
改成下面這樣後,看judge出來的結果所花的時間需要不到一半。

class Solution:   
    def longestContinuousSubstring(self, s: str) -> int:
        c,maxC = 1,1
        for i in range(1,len(s)):
            if ord(s[i])-1 != ord(s[i-1]):
                c=1
            else:
                c+=1
            maxC = max(maxC,c)
        return maxC

接著是 2409. Count Days Spent Together (easy)
https://leetcode.com/problems/count-days-spent-together/

有兩個人,題目會跟你說A在幾月幾號來到某地方,然後在幾月幾號離開;B亦同,然後問說他們會有幾天待在同個地方。

這道題目大概也算是基礎題吧,概念上跟算西元xx年幾月幾日是第幾天差不多,我覺得難點反而落在數學的部分,要怎麼樣判斷他們是否有在同個地方。
想法,前綴和:

  1. 算出每個月天數的前綴和
  2. 計算四個日期在該年的第幾天
  3. 寫出是否在同一個地方的判斷規則(A進來的時間 < B離開的時間 or B進來的時間 > B離開的時間 代表沒碰到)
  4. 在同一個地方的話就找出兩個最早的離開時間扣掉兩人最晚進來的時間,最後要加一。
class Solution:
    def countDaysTogether(self, arriveAlice: str, leaveAlice: str, arriveBob: str, leaveBob: str) -> int:
        week = [0,31,59,90,120,151,181,212,243,273,304,334,365]
        def changeToDay(s):
            m = int(s[:2])
            d = int(s[-2:])
            result = week[m-1] + d
            return result
        aA,lA,aB,lB = changeToDay(arriveAlice),changeToDay(leaveAlice),changeToDay(arriveBob),changeToDay(leaveBob)
        print(aA,lA,aB,lB)
        if lA < aB or lB < aA:
            return 0
        else:
            return min(lA,lB) - max(aA,aB)+1

接著是 2410. Maximum Matching of Players With Trainers (medium)
https://leetcode.com/problems/maximum-matching-of-players-with-trainers/

會有兩個串列,一個是球員的戰鬥力串列,一個是教練的戰鬥力串列,要一一配對,球員的戰力要小於等於教練。

想法:

  1. 排序,將球員跟教練進行排序
  2. 建立三個變數i(球員),j(教練),t(成功配對數),專門指現在在哪個教練或是球員以及是否配對成功
  3. 迭帶兩個串列進行比較,若球員戰力小於等於教練戰力則i,j,t都要加一,若沒有則j加一。
  4. return 結果
class Solution:
    def matchPlayersAndTrainers(self, p: List[int], tr: List[int]) -> int:
        p.sort()
        tr.sort()
        t = 0
        i,j = 0,0
        pL,tL = len(p),len(tr)
        while i<pL and j<tL:
            if p[i]<= tr[j]:
                t+=1
                i+=1
                j+=1
            else:
                j+=1
        return t

但這樣寫下來其實有點慢,所以為了減少比較次數,稍微進行了一些調整。
速度從judge的結果來看,所花時間大約少了50%

class Solution:
    def matchPlayersAndTrainers(self, p: List[int], tr: List[int]) -> int:
        p.sort()
        tr.sort()
        t = 0
        i,j = 0,0
        pL,tL = len(p),len(tr)
        while i<pL and j<tL:
            while j<tL and p[i] > tr[j]  :
                j+=1
            if j < tL:
                t+=1
                i+=1
                j+=1
        return t

今天就大概這樣吧,感謝大家觀看。


上一篇
Day2 隨機挑題
下一篇
Day4 隨機挑題
系列文
leetcode 30天 不中斷解題挑戰30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言